# coding=utf-8
__author__ = 'st316'
'''
Given an array and a value, remove all instances of that value in place and return the new length.

The order of elements can be changed. It doesn't matter what you leave beyond the new length.
两个游标：
i从左开始扫描，j记录从右开始第一个不等于elem的元素的index，别忘记推出循环时候的最后判断
'''


class Solution:
    # @param    A       a list of integers
    # @param    elem    an integer, value need to be removed
    # @return an integer
    def removeElement(self, A, elem):
        l = len(A) - 1
        if l < 0:
            return 0
        i = 0
        while i < l:
            if A[i] == elem:
                l = self.swap(A, i, l, elem)
            i += 1
        if l > -1:
            return l + 1 if A[l] != elem else l
        return l + 1

    def swap(self, A, i, j, elem):
        assert A[i] == elem
        while A[j] == elem and i < j:
            j -= 1
        if i < j:
            A[i], A[j] = A[j], A[i]
            return j - 1
        else:
            return i - 1


if __name__ == '__main__':
    l = [33, 3, 3, 3, 3]
    s = Solution()
    print s.removeElement(l, 3)